package 滑动窗口And双指针.双指针.快慢指针;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/3/2 23:01
 */
public class 快慢指针判断链表的环 {

    /*
      比较容易理解的两个 视频的链接：

      判断 链表的 有环：
      https://www.bilibili.com/video/BV1Na411t7v2/?vd_source=179da737184de5a8f84e4f6c2ee5c350

      找到 链表的环的入口地址：
      https://www.bilibili.com/video/BV1Kq4y1v7yi/?spm_id_from=333.788.recommend_more_video.10&vd_source=179da737184de5a8f84e4f6c2ee5c350



     */

    /*
     找到环的 入口地址 ：  对应  lc： 142 环形链表 II
     然后， 让 一个 指针 从 head 开始走， 一个指针 从 相遇节点 Node 开始走， 相遇的 那个节点
     就是 环的入口 节点 （ 具体证明的 话， 看上面的链接
     */
    public class Solution {
        public Node detectCycle(Node head) {
          Node slow = head, fast = head;
            while(fast != null && fast.next != null){
                slow = slow.next;
                fast = fast.next.next;
                if(slow == fast){
                    slow = head;
                    while(slow != fast){
                        slow = slow.next;
                        fast = fast.next;
                    }
                    return slow;
                }
            }

            return null;
        }
    }


    /*
     对应 lc 141： 环形链表 I
     slow : 一次 走一步
     fast： 一次 走两步
    注意是链表的 一步和两步 :
    注意： 如果链表想要 形成 一个 环的 话， 必须 有至少 three Node
     */
    public boolean judgeCircle(Node head){
        if(head == null || head.next == null){
            return false;
        }
        /*
         这里 有一个 比较 致命的 错误， 就是  fast = head.next.next , slow = head
         fast 都已经 走两步, slow 却 还没走,  这样 写 再 lc 141 中是没有 任何问题的, 但是 再 lc 142 中就会出现 死循环
         要么 就不要这样写, 直接 像上面那样 把 判断直接放在 while  循环中 进行就可以,
         上面的 代码 就是最佳实践吧!

         */
        Node slow = head.next,fast = head.next.next;
        // 注意 一下 fast 是 直接 跳两步， 的 所以 fast。next 也需要判断 ！= null （避免空指针异常）
        while(slow != fast && fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        /*
         退出while 循环的话， 只有两种情况 ， ①：fast == slow ，说明 有环，   ② fast == null 说明 每环， 已经 走到链表的 tail
         */
        return slow == fast;
    }

   static class Node{
        int val;
        Node next;

        public Node(){

        }
        public Node(int val){
            this.val = val;
        }
    }

}
